Labeling process is one of key processes of an image processing for binary image data with black and white. Generally, a white pixel is defined as a background pixel and a black pixel is defined as a feature pixel. The labeling process is to assign with a label such as a number to feature pixels linking each other. Using the labeling process, it is possible to identify a plurality of targets in the image and to measure each area size and centroid of the target in the image.
As linking methods which link the pixels, there are mainly two methods that are a 4-linking method (4-neibourhood) and a 8-linking (8-neibourhood) method. In the 4-linking method, the target pixel and four pixels of upper, lower, left and right pixels to the target pixel are judged. In the 8-linking method, four more pixels at diagonal positions of the target pixel are judged in addition to the target pixel, the four pixels as described above.
FIG. 1 illustrates a flowchart of a background labeling method. Following three steps are performed with image data stored in a frame memory.
In step S02, a preliminary labeling (pre-labeling) process is performed. Preliminary labels are assigned and connecting information between the preliminary labels is generated during the pre-labeling process.
In step S04, a translation table for a primary labeling process is generated.
In step S06, the primary labeling process is performed. The preliminary labels are translated to primary labels referring to the translation table generated in the steps S04.
As a result of the above described labeling processes, labeled image data is output and is stored back into the frame memory. The image data stored in the frame memory is scanned sequentially at the both case of the pre-labeling process and the primary labeling process. A plurality of pixels of the image data are read and are translated sequentially.
When the labeling process is performed to binary image data stored in a two-dimensional storage such as a frame memory by the 4-linking method, it is required to scan the binary data sequentially from upper left to lower right of the image data. During the scanning, at least two pixels which are located neighboring at left side and at upper side to the target pixel are referred. This sequential processing causes a long processing time.
Further, it is requested that each pixel has a certain data width such as 8-bits-wide and 16-bits-wide to assign a labeling value. Accordingly, this causes a tradeoff relationship between a number of the labeling to be assigned and a storage capacity of the frame memory.
To shorten the labeling process time, it is proposed to assign a preliminary or a primary label to a plurality of pixels after reading and examining a scanned pixel pattern. This method attempts to obtain a high speed labeling procedure because overlapping at the scanning process is reduced. However, if two pixels are the target pixels, storage capacity for one pixel is increased with increase of the number of labels to be needed because the preliminary or the primary label is assigned to each pixel. Therefore, a breakthrough is highly requested both for achieving high speed labeling and for saving storage capacity of the frame memory.